// 带有堆优化的Dijkstra算法
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2005;

vector<int> G[N];  // 存图
ll a[N][N];  // 存边权，也可以写成结构体放到vector里，这样写的目的是便于理解
             // a[from][to]
int n;       // 点数
int m;       // 边数
struct node {  // 用来保存
    ll val;    // 权值
    int id;    // 节点编号
    bool operator<(const node& o) const { return val > o.val; }
    // 优先队列是大顶堆，而我们希望以距离权值排序，构建小顶堆，故重新定义堆内结构体节点排序规则
};
ll dis[N];  // 从起点到i点的
bool vis[N];
void dij(int ori) {              // 入参为原始起点
    memset(vis, 0, sizeof vis);  // 将所有点都标记为未访问
    fill(dis + 1, dis + n + 1, INT_MAX);  // 把起点到所有点的距离标记为正无穷
    dis[ori] = 0;                         // 起点距离起点为零
    priority_queue<node> pq;  // 优先队列 小顶堆
    pq.push({0, ori});
    while (!pq.empty()) {  // 堆内不为空
        int x = pq.top().id;
        pq.pop();  // 弹出堆顶节点，并将其编号存储在变量x里
        if (!vis[x]) {            // 如果x节点未访问过
            vis[x] = 1;           // 标记已访问
            for (int i : G[x]) {  // 遍历x的所有出度
                if (dis[x] + a[x][i] < dis[i]) {
                    // 如果经由x到i的距离比目前走到i的距离短
                    dis[i] = dis[x] + a[x][i];  // 则执行优化（松弛）
                    pq.push({dis[i], i});  // 并将i节点及其距离压入堆中
                }
            }
        }
    }
}
